Game

Limit pamięci: 8 MB

Dwaj gracze, i , grają w grę na kwadratowej planszy o rozmiarach . Pola planszy dzielą się na białe i czarne. Gra toczy się jedynie na białych polach. Każdy gracz ma swojego piona, początkowo ustawionego na polu startowym danego gracza - jednym z białych pól planszy. Pola startowe graczy i są różne.

W każdym ruchu gracz porusza swojego piona na jedno z sąsiadujących z jego pozycją białych pól (w górę, dół, lewo lub prawo). Jeśli gracz przesunie piona na pole zajmowane w tej samej chwili przez piona przeciwnika, otrzymuje dodatkowy ruch (w ten sposób przeskakuje nad pionem przeciwnika). Zauważ, że w takim przypadku kierunek drugiego ruchu może być różny od kierunku pierwszego ruchu.

Gracze poruszają się na zmianę, pierwszy ruch wykonuje gracz . Celem gry jest dojście własnym pionem do pola startowego przeciwnika. Gracz, który dokona tego wcześniej, wygrywa. W przypadku, gdy ruch gracza składa się z dwóch posunięć i jedynie przechodzi on przez pole startowe przeciwnika (w sytuacji, gdy przeciwnik stoi na swoim polu startowym), gracz również wygrywa. Dla danej sytuacji chcemy stwierdzić, który z graczy ma strategię wygrywającą (mówi się, że gracz ma strategię wygrywającą, jeśli może on wygrać grę niezależnie od ruchów przeciwnika).

Rysunek 1. Jeśli poruszy się trzykrotnie w prawo w swoich trzech pierwszych ruchach, odpowie na każdy ruch posunięciem w górę. Dlatego, w trzecim ruchu gracz wejdzie na pole zajmowane przez piona gracza i będzie mógł ruszyć się ponownie. Z tego powodu, wcześniej osiągnie pole startowe gracza i wygra.

Rysunek 2. może zacząć od ruchów w prawo i w dół. Później, zależnie od ruchów gracza , pójdzie albo w dół, albo w prawo tak, aby uniknąć spotkania pionów. W ten sposób szybciej dotrze do pola startowego , wygrywając grę. Dlatego też ma strategię wygrywającą w tym przypadku.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis planszy oraz punkty startowe obu zawodników,
• wyznaczy zawodnika, który ma strategią wygrywającą,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą , oznaczającą liczbę przypadków testowych do rozpatrzenia (). Po nim następuje kolejno opisów poszczególnych testów. Każdy z testów jest opisany w następujący sposób. Pierwszy wiersz zawiera jedną liczbę całkowitą (), oznaczającą długość boku planszy. Kolejnych wierszy zawiera opis planszy. Każdy z nich składa się z znaków (bez odstępów pomiędzy nimi). Każdy ze znaków to: '.' (białe pole) '#' (czarne pole), 'A' (pozycja startowa gracza ) lub 'B' (pozycja startowa gracza ).

Możesz założyć, że istnieje ścieżka składająca się z białych pól, łącząca punkty startowe graczy i .

Dodatkowo, w testach wartych 60% punktów, , zaś w testach wartych 40% punktów, .

Wyjście

Dla każdego zestawu testowego na wyjściu powinien znaleźć się dokładnie jeden wiersz zawierający pojedynczy znak 'A' lub 'B', oznaczający gracza, który posiada strategię wygrywającą.

Przykład

Dla danych wejściowych:

2
4
A...
.#..
....
...B
4
A...
....
..#.
...B

poprawną odpowiedzią jest:

B
A

Autor zadania: Jimmy Mårdell.